Năm 1511, Malacca rơi vào tay của người Bồ Đào Nha và quốc vương Mahmud Shah buộc phải tháo chạy khỏi Malacca. Nhà vua Malacca đã thực hiện một số nỗ lực để lấy lại vương quốc của mình nhưng không có kết quả. Người Bồ Đào Nha trả đũa và buộc nhà vua phải chạy trốn đến Pahang. Sau đó ông đã đến Bintan và thành lập một căn cứ mới ở đó, ông đã tập hợp lực lượng người Malay bị phân rả trước đó thực hiện một số cuộc tấn công và phong toả chống lại người Bồ Đào Nha.

Vương quốc Hồi giáo Johor được thành lập bởi Sultan Alauddin Riayat Shah (1528-1564) với hoàng hậu Tun Fatimah năm 1528. Mặt dù Alauddin Riayat Shah và người kế nhiệm ông đã phải đương đầu với những cuộc tấn công của người Bồ Đào Nha ở Malacca và Aceh ở Sumatra, nhưng họ vẫn giữ được chủ quyền của vương quốc Johor.

Các cuộc đánh phá thường xuyên vào Malacca đã gây ra nhiều khó khăn cho người Bồ Đào Nha, nó đã thuyết phục người Bồ Đào Nha tập trung tiêu diệt lực lượng Hồi giáo lưu vong. Một số nỗ lực đã được thực hiện để đàn áp người Malay, đến năm 1526 người Bồ Đào Nha đãn san phẳng Bintan. Sau đó vua Mahmud Shah phải rút về Kampar ở Sumatra và qua đời 2 năm sau đó, ông để lại hai con trai là Muzaffar Shah và Alauddin Riayat Shah II.

Muzaffar Shah tiếp tục thành lập Perak trong khi Alauddin Riayat Shah trở thành vị vua thứ nhất của Johor.